package JavaCode.contest.weekly.n0_200.n181;

/**
 * author:fangjie
 * time:2020/3/22
 */
public class N3 {
    public boolean hasValidPath(int[][] grid) {
        return dfs(0,0,grid,new boolean[grid.length][grid[0].length]);
    }
    private boolean dfs(int i, int j, int[][] grid,boolean[][] book) {
        if(i==grid.length-1&&j==grid[0].length-1)return true;
        book[i][j]=true;
        switch (grid[i][j])
        {
            case 1:
                if(left(i, j, grid, book))return true;
                if(right(i,j,grid,book))return true;
                break;
            case 2:
                if(up(i,j,grid,book))return true;
                if(down(i,j,grid,book))return true;
                break;
            case 3:
                if(left(i,j,grid,book))return true;
                if(down(i,j,grid,book))return true;
                break;
            case 4:
                if(right(i, j, grid, book))return true;
                if(down(i, j, grid, book))return true;
                break;
            case 5:
                if(up(i, j, grid, book))return true;
                if(left(i, j, grid, book))return true;
                break;
            case 6:
                if(up(i, j, grid, book))return true;
                if(right(i, j, grid, book))return true;
                break;
        }
        return book[i][j]=false;
    }

    private boolean left(int i, int j, int[][] grid, boolean[][] book) {
        if(j-1>=0&&(grid[i][j-1]==1||grid[i][j-1]==4||grid[i][j-1]==6)&&!book[i][j-1])
        {
            return dfs(i,j-1,grid,book);
        }
        return false;
    }
    private boolean right(int i,int j,int[][] grid,boolean[][] book)
    {
        if(j+1<grid[0].length&&(grid[i][j+1]==1||grid[i][j+1]==3||grid[i][j+1]==5)&&!book[i][j+1])
        {
            return dfs(i,j+1,grid,book);
        }
        return false;
    }
    private boolean up(int i, int j, int[][] grid, boolean[][] book)
    {
        if(i-1>=0&&(grid[i-1][j]==2||grid[i-1][j]==3||grid[i-1][j]==4)&&!book[i-1][j])
        {
            return dfs(i-1,j,grid,book);
        }
        return false;
    }
    private boolean down(int i, int j, int[][] grid, boolean[][] book)
    {
        if(i+1<grid.length&&(grid[i+1][j]==2||grid[i+1][j]==5||grid[i+1][j]==6)&&!book[i+1][j])
        {
            return dfs(i+1,j,grid,book);
        }
        return false;
    }
}
/*
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。


你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你 不能 变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。



示例 1：



输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。
示例 2：



输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。
示例 3：

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。
示例 4：

输入：grid = [[1,1,1,1,1,1,3]]
输出：true
示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true


提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6
 */
